1. Field of the Invention
The present invention relates to an automatic trace determination apparatus and an automatic trace determination method for determining trace routes, on a substrate and that do not intersect with obstacles on the substrate, automatically by computation, as well as to a computer program for allowing a computer to perform this automatic trace determination process.
2. Description of the Related Art
For example, in semiconductor integrated circuits such as LSIs (large-scale integrated circuits), PCBs (printed-circuit boards) and the like, as a typical example of a trace route search method for automatically providing traces without intersection with obstacles existing on a substrate, a method called a labyrinth search method is described, for example, in Japanese Unexamined Patent Publication No. H11-161694, Japanese Unexamined Patent Publication No. 2001-350813, Japanese Unexamined Patent Publication No. 2001-044288, and Japanese Unexamined Patent Publication No. H10-209288.
In the labyrinth search method, trace routes on a substrate are set so as to secure clearance from other traces or obstacles and so as not to intersect with the obstacles by diverting the trace route around such obstacles at 90 degrees or, in some cases, 45 degrees, which is an angle formed by the trace route and the verge of the substrate. Such a setting technique can be implemented, in particular, for LSIs, PCBs and the like, which have peculiar pattern characteristics in that disposed positions and the shapes of the obstacles in the LSIs, PCBs and the like have a certain regularity.
On substrates of PBGA, EBGA and the like semiconductor packages, there exist a large number of elements, such as planes, gates, marks, internal components or other traces in the packages, and so on, that may obstruct the traces and the shapes and the disposed positions or angles of such obstacles may vary significantly. Further, vias, balls, bonding pads (B/P), flip chip pads (F/C) or the like, which are to be starting or end points of the traces, may be positioned variously. Therefore, in trace design for the semiconductor packages, when the obstacles on the substrate are bypassed, the trace routes have to be diverted around the obstacles at arbitrary angles formed by the trace route and the verge of the substrate, which are not limited to 90 or 45 degrees. Thus, the labyrinth search method that has been conventionally used for automatic wiring in the LSI, PCB and the like cannot be applied to automatic wiring of the semiconductor packages.
In view of such circumstances, in the trace design of semiconductor packages, a designer typically designs the trace routes of the semiconductor packages on a virtual plane by trial and error depending on the designer's skill, experience and intuition, for example, by using a CAD system. In such manual trace design by trial and error, as the required traces become more complicated, the effort, time and difficulty for achieving the optimal traces is increased. Further, unevenness in quality of finished products is also increased. In reality, because the manual trace design by trial and error requires at least more than ten hours' work and it is not economical to spend more time on trace designing, the designer has to compromise with a certain design quality. As the semiconductor packages are miniaturized and integrated, automatization of trace design of the semiconductor packages will be one of the most important tasks in the future.
In view of the above problems, it is an object of the present invention to provide an automatic trace determination apparatus and an automatic trace determination method that can determine trace routes on a substrate, that do not intersect with obstacles on the substrate, automatically and in a short time, as well as a computer program for allowing a computer to perform this automatic trace determination process.